package com.berchen.数据结构.递归;

/**
 * 迷宫问题
 *
 * 1 1 1 1 1 1 1
 * 1 0 0 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 1 1 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 1 1 1 1 1 1
 *
 * 1 表示墙 不能走  0 表示还未走过 2 表示走过 可以通  3 表示走过 不通
 * 自定义策略：上 右 下 左  策略不同得到的路线也不同
 */
public class Maze {

    /**
     * 重点 map[6][5]
     * @param map 迷宫地图
     * @param i   从那个位置开始走
     * @param j   从那个位置开始走
     * @return
     */
    public boolean getWay(int[][] map,int i,int j ){

        if(map[6][5]==2){   // 先判断这个点是否走过 并且可通
            return true;
        }else {
            if(map[i][j]==0){   // 该点还没有走过
                map[i][j]=2;    // 先假设这个点能走通
                if(getWay(map,i-1,j)){  // 往上走
                    return true;
                }else if (getWay(map,i,j+1)){
                    return true;
                }else if (getWay(map,i+1,j)){
                    return true;
                }else if (getWay(map,i,j-1)){
                    return true;
                }else { // 上下左右都走了 走不通 就 设置改点走不通
                    map[i][j]=3;
                    return false;
                }
            }
            else{   // 1 墙 不能走 3 走过 不通  2 走过 可以通 （可以通的地方都不会走第二次，因为从上面的策略可以看出来  ）
                return false;
            }
        }
    }
}
